package com.xq.algorithm.string;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/10.
 */

public class KMPAlgorithm {

    public static int[] getNextArray(String s){
        char[] ch = s.toCharArray();
        int i,j;
        int[] next = new int[ch.length];
        for(i = 1,j = 0; i < ch.length; i++){
            while(j > 0 && ch[i] != ch[j]){
                j = next[j - 1];      //j <next[j - 1],所以向前移动
            }
            if(ch[i] == ch[j]){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    /**
     * @param str1 被匹配的字符串
     * @param str2  子串
     * @return 布尔值
     */
    public static boolean kmp(String str1,String str2){
        char[] strA = str1.toCharArray();
        char[] strB = str2.toCharArray();
        int[] next = getNextArray(str2);
        int i,j;  //这里i是从0开始的
        for(i = 0,j = 0; i < strA.length; i++){
            while(j > 0 && strA[i] != strB[j])
                j = next[j-1];
            if(strA[i] == strB[j]){
                j++;
            }
            //匹配成功
            if(j == strB.length){
                return true;
            }
        }
        return false;
    }
}
